﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0124_ZigzagLevelOrder : IAlgorithm
    {
        // 二叉树的锯齿形层次遍历

        // 给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

        // 提示：
        //  树中节点数目在范围[0, 2000] 内
        //  -100 <= Node.val <= 100

        public void Test()
        {
            // 算法参数定义
            var root =
                new TreeNode(1,
                    new TreeNode(2,
                        new TreeNode(4)
                        ),
                    new TreeNode(3,
                        null, new TreeNode(5)
                        )
                );
            // 算法执行与打印
            var res = ZigzagLevelOrder(root);
            foreach (var item in res)
            {
                foreach (var iitem in item)
                {
                    Console.Write(iitem + " ");
                }
                Console.WriteLine();
            }
        }

        // 算法
        // [3,9,20,null,null,15,7]
        public IList<IList<int>> ZigzagLevelOrder(TreeNode root)
        {
            var res = new List<IList<int>>();
            if (root == null)
                return res;
            var queue = new Queue<TreeNode>();
            queue.Enqueue(root);
            var leftFlag = true;
            while (queue.Count > 0)
            {
                int size = queue.Count;
                var resItem = new List<int>();
                for (int i = 0; i < size; i++)
                {
                    var temp = queue.Dequeue();
                    if (leftFlag)
                    {
                        resItem.Add(temp.val);
                    }
                    else
                    {
                        resItem.Insert(0, temp.val);
                    }
                    if (temp.left != null)
                        queue.Enqueue(temp.left);
                    if (temp.right != null)
                        queue.Enqueue(temp.right);
                }
                res.Add(resItem);
                leftFlag = !leftFlag;
            }
            return res;
        }
    }
}
